package chapter03_binaryTree;


import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 描述：
 * 二叉树按层打印和按ZigZag打印，输出必须为指定的格式
 *
 * @author hl
 * @date 2021/5/17 9:29
 */
public class PrintByLevelAndZigZag {
    public static void main(String[] args) {
        SerialBinaryTree serialBinaryTree = new SerialBinaryTree();
        PrintTree printTree = new PrintTree();
        Node head = serialBinaryTree.reconByLevel("1!2!3!4!#!5!6!#!#!7!8!#!#!#!#!#!#!");
//        printTree.printTree(head);
        PrintByLevelAndZigZag printByLevelAndZigZag = new PrintByLevelAndZigZag();
        System.out.println("按层打印：");
        printByLevelAndZigZag.printByLevel(head);
        System.out.println("ZigZag打印：");
        printByLevelAndZigZag.printByZigZag(head);
    }

    /**
     * 二叉树按层打印
     *
     * @param head
     */
    public void printByLevel(Node head) {
        if (head == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        Node last = head;
        Node nLast = null;
        Node cur = null;
        int n = 1;
        System.out.print("level " + n + ": ");
        while (!queue.isEmpty()) {
            cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
                nLast = cur.left;
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                nLast = cur.right;
            }
            if (cur == last && !queue.isEmpty()) {
                System.out.print("\nlevel " + ++n + ": ");
                last = nLast;
            }
        }
        System.out.println();
    }

    /**
     * 按ZigZag方式打印二叉树
     *
     * @param head
     */
    public void printByZigZag(Node head) {
        Deque<Node> dq = new LinkedList<>();
        dq.offer(head);
        int level = 1;
        Node last = head;//当前层最后一个打印的结点
        Node nLast = head.left;//下一层最后一个打印的结点
        System.out.print("level " + level + " from left to right : ");
        Node cur = head;
        boolean flag = true;
        while (!dq.isEmpty()) {
            if (flag) {
                cur = dq.pollFirst();
                if (cur.left != null) {
                    dq.offer(cur.left);
                }
                if (cur.right != null) {
                    dq.offer(cur.right);
                }
            } else {
                cur = dq.pollLast();
                if (cur.right != null) {
                    dq.offerFirst(cur.right);
                }
                if (cur.left != null) {
                    dq.offerFirst(cur.left);
                }
            }
            System.out.print(cur.val + " ");
            if (cur == last && !dq.isEmpty()) {
                System.out.print("\nlevel " + ++level + " from " + (flag ? "left " : "right ") + "to " + (flag ? "left " : "right ") + ": ");
                last = nLast;
                nLast = flag ? dq.peekLast().right : dq.peekFirst().left;
//                nLast = null;
                flag = !flag;
            }
        }
    }
}
